#ifndef MTNS_H_
#define MTNS_H_

#include <algorithm>
#include <functional>
#include <type_traits>
#include <utility>
#include <vector>

namespace lxj
{
// 单调栈求每个位置左右两侧，离当前位置最近、且值严格小于的位置
// 给定一个可能含有重复值的数组 arr
// 找到每一个 i 位置左边和右边离 i 位置最近且值比 arr[i] 小的位置
// 返回所有位置相应的信息。
// 输入描述：
// 第一行输入一个数字 n，表示数组 arr 的长度。
// 以下一行输入 n 个数字，表示数组的值
// 输出描述：
// 输出n行，每行两个数字 L 和 R，如果不存在，则值为 -1，下标从 0 开始。
// 测试链接 : https://www.nowcoder.com/practice/2a2c00e7a88a498693568cef63a4b7bb
template<class Relation,
         std::enable_if_t<std::is_same_v<std::greater<>, Relation> ||
                              std::is_same_v<std::less<>, Relation>,
                          int> = 0>
class MonoStack {
    inline constexpr static int MAXN        = 1000001;
    inline static int           stack[MAXN] = {};
    inline static int           r           = 0;

    inline void clear() { std::fill(stack, stack + MAXN, 0); }

    inline auto getType()
    {
        if constexpr (std::is_same_v<std::less<>, Relation>)
            return std::greater_equal<>();
        else
            return std::less_equal<>();
    }

    inline void compute(const std::vector<int>& arr, std::vector<std::pair<int, int>>& ans)
    {
        auto relation = this->getType();
        r             = 0;
        // 遍历阶段
        int cur;
        for (int i = 0; i < arr.size(); i++) {
            while (r > 0 && relation(arr[stack[r - 1]], arr[i])) {
                cur             = stack[--r];
                ans[cur].first  = r > 0 ? stack[r - 1] : -1;
                ans[cur].second = i;
            }
            stack[r++] = i;
        }
        // 清算阶段
        while (r > 0) {
            cur             = stack[--r];
            ans[cur].first  = r > 0 ? stack[r - 1] : -1;
            ans[cur].second = -1;
        }

        // 修正阶段
        // 左侧的答案不需要修正一定是正确的，只有右侧答案需要修正
        // 从右往左修正，n-1位置的右侧答案一定是-1，不需要修正
        for (int i = arr.size() - 2; i >= 0; i--) {
            if (ans[i].second != -1 && arr[ans[i].second] == arr[i]) {
                ans[i].second = ans[ans[i].second].second;
            }
        }
    }

public:
    inline std::vector<std::pair<int, int>> operator()(const std::vector<int>& vec)
    {
        std::vector<std::pair<int, int>> ans(vec.size());
        compute(vec, ans);
        return ans;
    }
};

// 每日温度
// 给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer
// 其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后
// 如果气温在这之后都不会升高，请在该位置用 0 来代替。
// 测试链接 : https://leetcode.cn/problems/daily-temperatures/
inline std::vector<int> dailyTemperatures(const std::vector<int>& temperatures)
{
    std::vector<int> ans(temperatures.size());
    auto             temp = MonoStack<std::greater<>>()(temperatures);
    int              i    = 0;
    std::transform(temp.cbegin(), temp.cend(), ans.begin(), [&i](const std::pair<int, int>& p) {
        return p.second != -1 ? p.second - (i++) : (++i) - i;
    });
    return ans;
}

// 子数组的最小值之和
// 给定一个整数数组 arr，找到 min(b) 的总和，其中 b 的范围为 arr 的每个（连续）子数组。
// 由于答案可能很大，答案对 1000000007 取模
// 测试链接 : https://leetcode.cn/problems/sum-of-subarray-minimums/
inline int sumSubarrayMins(std::vector<int>& arr)
{
    constexpr int MOD          = 1000000007;
    static int    stack[30001] = {};
    long long     ans          = 0;
    int           r            = 0;
    for (int i = 0; i < arr.size(); i++) {
        while (r > 0 && arr[stack[r - 1]] >= arr[i]) {
            int cur  = stack[--r];
            int left = r == 0 ? -1 : stack[r - 1];
            ans      = (ans + (long long)(cur - left) * (i - cur) * arr[cur]) % MOD;
        }
        stack[r++] = i;
    }

    while (r > 0) {
        int cur  = stack[--r];
        int left = r == 0 ? -1 : stack[r - 1];
        ans      = (ans + (long long)(cur - left) * (arr.size() - cur) * arr[cur]) % MOD;
    }
    return (int)ans;
}

// 柱状图中最大的矩形
// 给定 n 个非负整数，用来表示柱状图中各个柱子的高度
// 每个柱子彼此相邻，且宽度为 1 。求在该柱状图中，能够勾勒出来的矩形的最大面积
// 测试链接：https://leetcode.cn/problems/largest-rectangle-in-histogram
inline int largestRectangleArea(std::vector<int>& heights)
{
    static int stack[50001] = {};
    int        r            = 0;
    int        ans          = 0, cur, left;
    for (int i = 0; i < heights.size(); i++) {
        while (r > 0 && heights[stack[r - 1]] >= heights[i]) {
            cur  = stack[--r];
            left = r == 0 ? -1 : stack[r - 1];
            ans  = std::max(ans, (i - left - 1) * heights[cur]);
        }
        stack[r++] = i;
    }

    while (r > 0) {
        cur  = stack[--r];
        left = r == 0 ? -1 : stack[r - 1];
        ans  = std::max(ans, (int)(heights.size() - left - 1) * heights[cur]);
    }
    return ans;
}

// 最大矩形
// 给定一个仅包含 0 和 1 、大小为 rows * cols 的二维二进制矩阵
// 找出只包含 1 的最大矩形，并返回其面积
// 测试链接：https://leetcode.cn/problems/maximal-rectangle/
inline int maximalRectangle(std::vector<std::vector<char>>& matrix)
{
    std::vector<int> heights(matrix[0].size());
    int              ans = 0;
    for (int i = 0; i < matrix.size(); i++) {
        int j = 0;
        std::transform(
            matrix[i].cbegin(), matrix[i].cend(), heights.begin(), [&j, &heights](char i) {
                return i == '0' ? (++j) - j : heights[j++] + 1;
            });
        ans = std::max(ans, largestRectangleArea(heights));
    }
    return ans;
}
}   // namespace lxj

#endif